package org.ruanjj.lettercombinations;

import java.util.*;

//广度优先
public class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return new ArrayList<>();
        }
        Queue<String> letterQueue = new LinkedList<>();
        Map<Character,String> letterMap = Map.of('2',"abc",'3',"def",'4',"ghi",'5',"jkl",
                '6',"mno",'7',"pqrs",'8',"tuv",'9',"wxyz");

        String firstString = letterMap.get(digits.charAt(0));
        for(int j = 0; j<firstString.length();j++){
            letterQueue.add(String.valueOf(firstString.charAt(j)));
        }

        for(int i = 1; i < digits.length(); i++){
            int n = 0;
            int count = letterQueue.size();
            while(n < count){
                String topString = letterQueue.poll();
                String letter = letterMap.get(digits.charAt(i));
                for(int j = 0; j<letter.length();j++){
                    String addString = String.valueOf(letter.charAt(j));
                    if(null != topString){
                        addString = topString+addString;
                    }
                    letterQueue.add(addString);
                }
                n++;
            }
        }
        return letterQueue.stream().toList();
    }
}
